package com.gitee.ywj1352.算法.week02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 子集 {

    public static List<List<Integer>> subsets(int[] nums) {
        boolean[] status = new boolean[nums.length];
        List<List<Integer>> res = new ArrayList<>();
        doSubsets2(nums, status, 0, res);
        return res;
    }

    public static void doSubsets(int[] nums, boolean[] status, int level, List<List<Integer>> res) {
        if (level == nums.length - 1) {
            List<Integer> integers = new ArrayList<>();
            for (int i = 0; i < status.length; i++) {
                if (status[i]) integers.add(nums[i]);
            }
            res.add(integers);
            return;
        }
        //设置状态
        status[level] = false;
        doSubsets(nums, status, level + 1, res);
        //回溯状态
        status[level] = true;
        doSubsets(nums, status, level + 1, res);
    }


    public static void doSubsets2(int[] nums, boolean[] status, int level, List<List<Integer>> res) {
        if (level == nums.length) {
            List<Integer> integers = new ArrayList<>();
            for (int i = 0; i < status.length; i++) {
                if (status[i]) integers.add(nums[i]);
            }
            res.add(integers);
            return;
        }
        //不回溯状态就必须拷贝
        boolean[] b1 = Arrays.copyOf(status, status.length);
        b1[level] = false;
        boolean[] b2 = Arrays.copyOf(status, status.length);
        b1[level] = true;
        doSubsets2(nums, b1, level + 1, res);
        doSubsets2(nums, b2, level + 1, res);
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        List<List<Integer>> res = subsets(arr);
        for (List<Integer> list : res) {
            System.out.println(list);
        }
    }
}
